{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0. 0. 0. ... 0. 0. 0.]\n",
      " [0. 0. 0. ... 0. 0. 0.]\n",
      " [0. 0. 0. ... 0. 0. 0.]\n",
      " ...\n",
      " [0. 0. 0. ... 0. 0. 0.]\n",
      " [0. 0. 0. ... 0. 0. 0.]\n",
      " [0. 0. 0. ... 0. 0. 0.]]\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "def is_in_poly(x, y, polygon):\n",
    "    \"\"\"\n",
    "    whether one point is inside a 2-D poly\n",
    "    :param x: point_x\n",
    "    :param y: point_y\n",
    "    :param polygon: array of polygon vertex：k * 2\n",
    "    :return: true or false\n",
    "    \"\"\"\n",
    "    poly_xs = polygon[:, 0]\n",
    "    poly_ys = polygon[:, 1]\n",
    "    odd_cross = False\n",
    "    for i in range(len(poly_xs)):\n",
    "        j = i - 1 if i > 0 else len(poly_xs) - 1\n",
    "        if poly_ys[i] < y <= poly_ys[j] or poly_ys[j] < y <= poly_ys[i]:\n",
    "            if poly_xs[i] + (y - poly_ys[i]) * (poly_xs[j] - poly_xs[i]) / (poly_ys[j] - poly_ys[i]) < x:  # wont divide 0\n",
    "                odd_cross = False if odd_cross else True\n",
    "    return odd_cross\n",
    "\n",
    "\n",
    "def graph_in_poly(graph, polygon):\n",
    "    \"\"\"\n",
    "    setting pixel to one if the pixel in polygon\n",
    "    :param graph: a 2-D graph: m * m arraty\n",
    "    :param polygon: array of polygon vertex：k * 2\n",
    "    :return: new 2-D array\n",
    "    \"\"\"\n",
    "    \n",
    "    new_graph = graph\n",
    "    \n",
    "    for i in range(graph.shape[0]):\n",
    "        for j in range(graph.shape[1]):\n",
    "            if is_in_poly(i,j, polygon):\n",
    "                new_graph[i, j] = 1\n",
    "    \n",
    "    return new_graph\n",
    "\n",
    "m = 80\n",
    "\n",
    "graph = np.zeros([m,m])\n",
    "\n",
    "polygon_array = np.array([[40.1, 40.1], [60.1, 30.1], [20.1, 20.1], [50.1, 30.1]])\n",
    "\n",
    "new_graph = graph_in_poly(graph, polygon_array)\n",
    "\n",
    "print(new_graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(80, 80)"
      ]
     },
     "execution_count": 83,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "new_graph.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAP4AAAD8CAYAAABXXhlaAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvFvnyVgAADJZJREFUeJzt3V+MHeV9xvHvUxvjQoqMaUAOpgUkRECVMKkViOgFhbohKYJchAiUVihF8k1agZQqgdxVaiVyk5CLKhIipL6gAUpAsVAERQ6orVS5mOD8AceFUAorE0wDiJSoNE5+vThjsqVrdnbPn93Z9/uRjs6ZOXN23tHoOe/Me2bnl6pCUlt+baUbIGn2DL7UIIMvNcjgSw0y+FKDDL7UIIMvNWis4Ce5IsnBJM8muXlSjZI0XVnuBTxJ1gH/BuwA5oDHgeuq6unJNU/SNKwf47MfBJ6tqucAktwNXA0cM/gbcnxt5MQxVinp3fw3b/I/9VYWW26c4J8OvDhveg646N0+sJETuSiXj7FKSe9mb+3ptdw4wV/oW+X/nTck2QnsBNjICWOsTtKkjDO4NwecMW96K3DonQtV1e1Vtb2qth/H8WOsTtKkjBP8x4FzkpyVZANwLbB7Ms2SNE3LPtSvqiNJ/gx4GFgH3FlVT02sZZKmZpxzfKrqW8C3JtQWSTPilXtSgwy+1CCDLzXI4EsNMvhSgwy+1CCDLzXI4EsNMvhSgwy+1CCDLzXI4EsNMvhSgwy+1CCDLzXI4EsNMvhSgwy+1KBFg5/kziSHk/xg3rzNSR5J8kz3fPJ0mylpkvr0+H8LXPGOeTcDe6rqHGBPNy1pIBYNflX9I/DqO2ZfDezqXu8CPjbhdkmaouWe459WVS8BdM+nTq5JkqZtrNtr92EJLWn1WW6P/3KSLQDd8+FjLWgJLWn1WW7wdwPXd6+vB745meZImoU+P+d9HfgX4Nwkc0luAG4FdiR5BtjRTUsaiEXP8avqumO8ZaF7aaC8ck9qkMGXGmTwpQYZfKlBBl9qkMGXGmTwpQYZfKlBBl9qkMGXGmTwpQYZfKlBBl9qkMGXGmTwpQYZfKlBBl9qkMGXGtTnnntnJHk0yYEkTyW5sZtvGS1poPr0+EeAz1TVecDFwKeTnI9ltKTB6lNC66Wq+k73+qfAAeB0LKMlDdaSzvGTnAlcCOzFMlrSYPUOfpL3AN8AbqqqN5bwuZ1J9iXZ93PeWk4bJU1Yr+AnOY5R6O+qqvu72b3KaFlCS1p9+ozqB/gqcKCqvjjvLctoSQPVp1ruJcCfAN9Psr+b93lGZbPu7UpqvQBcM50mSpq0PiW0/hnIMd62jJY0QF65JzXI4EsN6nOOryV4+ND+t19/+H3bVrAl0rHZ40sNssefMHt5DYE9vtQggy81yOBLDTL4UoMMvtQgR/WnyN/0tVrZ40sNMvhSgwy+1CCDLzXIwb0pckBPq5U9vtQggy81yODPyMOH9v+f3/WlldTnLrsbk/xrku92tfP+spt/VpK9Xe28e5JsmH5zJU1Cnx7/LeCyqroA2AZckeRi4AvAl7raea8BN0yvmZImqU/tvKqq/+omj+seBVwG3NfNt3aeNCB9K+ms6+6pfxh4BPgR8HpVHekWmWNUSHOhz1pCS1plegW/qn5RVduArcAHgfMWWuwYn7WElrTKLGlUv6peBx4DLgY2JTl6AdBW4NBkmyZpWvqM6r83yabu9a8DfwAcAB4FPt4tZu08aUD6XLK7BdiVZB2jL4p7q+rBJE8Ddyf5K+BJRoU1dQxHL9/1f/S1GvSpnfc94MIF5j/H6Hxf0sB45Z7UIIMvNcjgSw0y+FKDDL7UIIMvNchbb60gf9PXSrHHlxpk8KUGeag/Y/MP6b0Vl1aKPb7UIIMvNcjgSw0y+FKDDL7UIEf1Vwkv5tEs2eNLDTL4UoN6B7+7t/6TSR7spi2hJQ3UUnr8GxndXfcoS2hJA9W3ks5W4I+AO7rpYAmtsX34fdvefkiz1LfHvw34LPDLbvoULKElDVafghpXAoer6on5sxdY1BJa0kD0+R3/EuCqJB8FNgInMToC2JRkfdfrW0Jrgo7+pu8pgKalT5nsW6pqa1WdCVwLfLuqPokltKTBGufKvc9hCa01yasI174lBb+qHmNULdcSWtKAeeWe1CD/SUdvc1CxHfb4UoMMvtQgD/VXiYXuvjuL0XXv9Nsme3ypQQZfapCH+g061uG9o/ntsMeXGmSP3wgH8TSfPb7UIIMvNchD/YFY7m/6ix3iO6DXJnt8qUEGX2qQh/qr0NHD7+WOxDuCr8XY40sNMvhSg3od6id5Hvgp8AvgSFVtT7IZuAc4E3ge+ERVvTadZmoxSzm8dyRfS+nxf7+qtlXV9m76ZmBPV0JrTzctaQDGGdy7Gri0e72L0U04Pzdme9SDg3caV98ev4B/SPJEkp3dvNOq6iWA7vnUaTRQ0uT17fEvqapDSU4FHknyw74r6L4odgJs5IRlNFHSpPUKflUd6p4PJ3mA0f30X06ypapeSrIFOHyMz94O3A5wUjYvWF9P0+eAnubrUzTzxCS/cfQ18IfAD4DdjEpngSW0pEHp0+OfBjyQ5Ojyf1dVDyV5HLg3yQ3AC8A102umpElaNPhdqawLFpj/E+DyaTRKIwvdeVeaBK/ckxrkP+mscQ7qaSH2+FKDDL7UIIMvNcjgSw0y+FKDHNVfgxzJ12Ls8aUGGXypQR7qD4SX72qS7PGlBtnjrxEO6Gkp7PGlBhl8qUEGX2qQwZcaZPClBvUtobUJuAP4HUb32P9T4CCW0FpRjuRrufr2+F8GHqqq9zO6/94BLKElDVaq3v1W90lOAr4LnF3zFk5yELh03n31H6uqc9/tb52UzXVRvD+nNC17aw9v1KtZbLk+Pf7ZwCvA15I8meSO7v76ltCSBqpP8NcDHwC+UlUXAm+yhMP6JDuT7Euy7+e8tcxmSpqkPsGfA+aqam83fR+jL4KXu0N8FiuhVVXbq2r7cRw/iTZLGtOiwa+qHwMvJjl6/n458DSW0JIGq+8/6fw5cFeSDcBzwKcYfWlYQksaoL7VcvcD2xd4yyF6aYC8ck9qkMGXGmTwpQYZfKlBBl9qkMGXGmTwpQYZfKlBBl9qkMGXGmTwpQYZfKlBBl9qkMGXGmTwpQYZfKlBBl9qkMGXGrRo8JOcm2T/vMcbSW5KsjnJI0me6Z5PnkWDJY2vz112D1bVtqraBvwu8DPgASyhJQ3WUg/1Lwd+VFX/AVwN7Orm7wI+NsmGSZqepQb/WuDr3WtLaEkD1Tv43T31rwL+fikrsISWtPospcf/CPCdqnq5m7aEljRQSwn+dfzqMB8soSUNVq/gJzkB2AHcP2/2rcCOJM907906+eZJmoa+JbR+Bpzyjnk/wRJa0iB55Z7UIIMvNcjgSw0y+FKDDL7UIIMvNcjgSw0y+FKDDL7UIIMvNcjgSw0y+FKDDL7UIIMvNcjgSw0y+FKDDL7UIIMvNcjgSw0y+FKDDL7UoFTV7FaWvAK8CfznzFY6W7/J2tw2t2s4fruq3rvYQjMNPkCSfVW1faYrnZG1um1u19rjob7UIIMvNWglgn/7CqxzVtbqtrlda8zMz/ElrTwP9aUGzTT4Sa5IcjDJs0lunuW6JynJGUkeTXIgyVNJbuzmb07ySJJnuueTV7qty5FkXZInkzzYTZ+VZG+3Xfck2bDSbVyOJJuS3Jfkh92++9Ba2WdLNbPgJ1kH/A3wEeB84Lok589q/RN2BPhMVZ0HXAx8utuWm4E9VXUOsKebHqIbgQPzpr8AfKnbrteAG1akVeP7MvBQVb0fuIDRNq6VfbY0VTWTB/Ah4OF507cAt8xq/VPetm8CO4CDwJZu3hbg4Eq3bRnbspVRAC4DHgTC6CKX9Qvtx6E8gJOAf6cb15o3f/D7bDmPWR7qnw68OG96rps3aEnOBC4E9gKnVdVLAN3zqSvXsmW7Dfgs8Mtu+hTg9ao60k0Pdb+dDbwCfK07jbkjyYmsjX22ZLMMfhaYN+ifFJK8B/gGcFNVvbHS7RlXkiuBw1X1xPzZCyw6xP22HvgA8JWqupDRpeNtHNYvYJbBnwPOmDe9FTg0w/VPVJLjGIX+rqq6v5v9cpIt3ftbgMMr1b5lugS4KsnzwN2MDvdvAzYlWd8tM9T9NgfMVdXebvo+Rl8EQ99nyzLL4D8OnNONEG8ArgV2z3D9E5MkwFeBA1X1xXlv7Qau715fz+jcfzCq6paq2lpVZzLaP9+uqk8CjwIf7xYb3HYBVNWPgReTnNvNuhx4moHvs+Wa9X/nfZRRD7IOuLOq/npmK5+gJL8H/BPwfX51Lvx5Ruf59wK/BbwAXFNVr65II8eU5FLgL6rqyiRnMzoC2Aw8CfxxVb21ku1bjiTbgDuADcBzwKcYdX5rYp8thVfuSQ3yyj2pQQZfapDBlxpk8KUGGXypQQZfapDBlxpk8KUG/S9mKE8xFIHsqAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.imshow(new_graph)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD8CAYAAACMwORRAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4wLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvFvnyVgAAGA5JREFUeJzt3V1sXOd95/Hvj6T4TomkRFK0ZFlU7LVjZGPZ4XqdehGkVtwm2SD2RVI4uyi0CwO66W6TtovG2QU2W6AXDlA0zUU3hRCnVYus7cSx14Yv0ni1Sdy0GzWUZUuyKFmSLcuUZJKS+KZXvv33Yg5pkqLMGXKGMzz8fQDizDlzDs8fnJmfHj3znOcoIjAzs3QpK3YBZmaWfw53M7MUcribmaWQw93MLIUc7mZmKeRwNzNLoazCXdIfSHpT0mFJT0uqltQhaZ+k45KelVRZ6GLNzCw7C4a7pE3A7wOdEfExoBx4DPgW8O2IuAMYAB4vZKFmZpa9bLtlKoAaSRVALXAOeAh4Lnl+D/Bo/sszM7PFqFhoh4g4I+nPgNPAVeCnwH5gMCLGk916gE3zHS9pF7ALoK6u7hN33XVXPuo2M1s19u/ffz4iWnI5ZsFwl9QEPAJ0AIPAj4DPzbPrvPMYRMRuYDdAZ2dndHV15VKfmdmqJ+ndXI/JplvmM8A7EdEfEWPA88BvAI1JNw3AZuBsric3M7PCyCbcTwMPSKqVJGAHcAT4GfClZJ+dwIuFKdHMzHK1YLhHxD4yX5y+BhxKjtkNfB34Q0kngPXAUwWs08zMcrBgnztARHwT+OaczW8D9+e9IjMzWzJfoWpmlkIOdzOzFHK4m5mlkMPdzCyFHO5mZinkcDczSyGHu5lZCjnczcxSyOFuZpZCDnczsxRyuJuZpZDD3cwshRzuZmYp5HA3M0shh7uZWQo53M3MUsjhbmaWQg53M7MUWjDcJd0p6fUZP8OSviapWdIrko4ny6blKNjMzBaWzQ2yj0XE9ojYDnwCuAK8ADwB7I2IO4C9ybqZmZWAXLtldgAnI+Jd4BFgT7J9D/BoPgszM7PFyzXcHwOeTh63RcQ5gGTZms/CzMxs8bIOd0mVwBeBH+VyAkm7JHVJ6urv78+1PjMzW4RcWu6fA16LiN5kvVdSO0Cy7JvvoIjYHRGdEdHZ0tKytGrNzCwruYT7V/igSwbgJWBn8ngn8GK+ijIzs6XJKtwl1QIPA8/P2Pwk8LCk48lzT+a/PDMzW4yKbHaKiCvA+jnbLpAZPWNmZiXGV6iamaWQw93MLIUc7mZmKeRwNzNLIYe7mVkKOdzNzFLI4W5mlkIOdzOzFHK4m5mlkMPdzCyFHO5mZinkcDczSyGHu5lZCjnczcxSyOFuZpZCDnczsxRyuJuZpZDD3cwshRzuZmYplO0NshslPSfpqKRuSZ+U1CzpFUnHk2VToYs1M7PsZNty/w7wk4i4C7gH6AaeAPZGxB3A3mTdzMxKwILhLmkt8CngKYCIGI2IQeARYE+y2x7g0UIVaWZmucmm5b4N6Af+WtIBSd+TVAe0RcQ5gGTZOt/BknZJ6pLU1d/fn7fCzczs5rIJ9wrgPuC7EXEvcJkcumAiYndEdEZEZ0tLyyLLNDOzXGQT7j1AT0TsS9afIxP2vZLaAZJlX2FKNDOzXC0Y7hHxPvCepDuTTTuAI8BLwM5k207gxYJUaGZmOavIcr//DPxAUiXwNvAfyfzD8ENJjwOngS8XpkQzM8tVVuEeEa8DnfM8tSO/5ZiZWT74ClUzsxRyuJuZpZDD3cwshRzuZmYp5HA3M0shh7uZWQo53M3MUsjhbmaWQg53M7MUcribmaWQw93MLIUc7mZmKeRwNzNLIYe7mVkKOdzNzFLI4W5mlkIOdzOzFHK4m5mlUFa32ZN0ChgBJoDxiOiU1Aw8C2wFTgG/ExEDhSnTzMxykUvL/TcjYntETN1L9Qlgb0TcAexN1s3MrAQspVvmEWBP8ngP8OjSyzEzs3zINtwD+Kmk/ZJ2JdvaIuIcQLJsne9ASbskdUnq6u/vX3rFZma2oKz63IEHI+KspFbgFUlHsz1BROwGdgN0dnbGImo0M7McZdVyj4izybIPeAG4H+iV1A6QLPsKVaSZmeVmwXCXVCepYeox8FvAYeAlYGey207gxUIVaWZmucmmW6YNeEHS1P7/KyJ+IunXwA8lPQ6cBr5cuDLNzCwXC4Z7RLwN3DPP9gvAjkIUZWZmS+MrVM3MUsjhbmaWQg53M7MUcribmaWQw93MLIUc7mZmKeRwNzNLIYe7mVkKOdzNzFLI4W5mlkIOdzOzFHK4m5mlkMPdzCyFHO5mZinkcDczSyGHu5lZCjnczcxSyOFuZpZCWYe7pHJJByS9nKx3SNon6bikZyVVFq5MMzPLRS4t968C3TPWvwV8OyLuAAaAx/NZmJmZLV5W4S5pM/Bvge8l6wIeAp5LdtkDPFqIAs2Ww+TkJBFR7DLM8ibblvtfAH8MTCbr64HBiBhP1nuATfMdKGmXpC5JXf39/Usq1qxQysrKOH/mIsd+fYLzZy4wOTm58EFmJWzBcJf0BaAvIvbP3DzPrvM2eyJid0R0RkRnS0vLIss0K7yWzevZ+rFbOd19hv/zd6/yxi/epO90PxMTE8UuzSxnFVns8yDwRUmfB6qBtWRa8o2SKpLW+2bgbOHKNFseVTVV3PeZj/P+qT4O//IoPcfOUlFZQeuWDbRva6Nl83rKK8qLXabZgpRLP6OkTwP/JSK+IOlHwI8j4hlJfwUcjIj/+WHHd3Z2RldX15IKNlsuo9fHOLrvOO8dPTO9rbyinNYtG9jY0Urrlg1UrMmmfWS2NJL2R0RnLscs5Z35deAZSX8KHACeWsLvMis5lVVr+Pin7uaWj7Rx8NVuro5cZWJ8gnNv93Lu7V7KysvYsHk97R2ttN7WQmXVmmKXbDYtp5b7UrnlbivVxPgEx359gncOnZ73eZWVsf6WJtq3tbFxawuV1b7sw/JnuVvuZqtGeUU5d3/yTtq3tXHwF0e4NHh51vMxOcn5nguc77nA4X8Qze1NbOxopW1rCzV11UWq2lYzt9zNcjQxMcGJA6c4+fopIoshk01tjWzsaGVjRyu1DTXLUKGljVvuZsugvLycOzs/QntHK2/84gjD54c/dP+B3kEGegfp/tVbrN2wlvZtrbR3tFK3rm6ZKrbVyC13syWYnJzknUOneavrJJMTuV341NBcP92iX9vcUKAKLQ3ccjdbZmVlZXzknq1s3NrCwVe7uXhuIOtjRy5eYuTiJY7vf5u6dbVs7GilfVsb6zasLWDFtlq45W6WJxHB6e4euvedYGJsfOEDbqKmoSYT9B2tNLauIzOVk61mbrmbFZEkbrv7Vlq3bODwL4/Sd/r8on7P1ZGrvHPwXd45+C5VtVXTXTfNGxspK/MtGCw7brmbFciZE+c48k9vMXptNC+/r7K6kratLbRva2P9LU0O+lXELXezErLp9nY2bGrmzX96i3Mn31/y7xu9Nsp7R8/w3tEzVFRWsHFrpkW/YXMz5eWe78Zmc7ibFVBVTRX37fiX9N6+kUP/0M31K9fz8nvHR8fpeessPW+dpXxNMrFZMt+NJzYzcLibLYu221pobm+k+1ezJyLLh4mxcc6dfJ9zJ9+nvKI8M9/NtkzQr6n0fDerlcPdbJmsqUwmIrt9I4de7ebK8JW8n2NifILeU330nupDZWW0bG7OTINwm+e7WW0c7mbLbMMtzXzqSw9wrOskpw6dLtjt/WJykr7T5+k7fR5JrL9lar6bVqprqwpyTisdHi1jVkQDfUOZicgGLi3reZs2Nk7PYFlT7/luSt1iRss43M2KbHJykhMH3uHEgewmIsu3xtZ102Pp69bWLvv5bWEeCmm2ApWVlfEvPvERNna0cvAXRxjq//CJyPJtsG+Iwb4hju47ztr1DdPTINQ3emKzlcwtd7MSEhHTE5FNjBf3xtz1jXVs3NZGe0cra9d7YrNicreMWUpcHr7CoVe7uXD2YrFLAaB2be10101T67pil7PqFCTcJVUDrwJVZLpxnouIb0rqAJ4BmoHXgN+NiA+9ztrhbpab00fP0P2rtxgfXfxEZPlWU19N29ZW2re10tTW6InNlkGhwl1AXURckrQG+CXwVeAPgecj4hlJfwW8ERHf/bDf5XA3y93Vy9cyE5G921/sUm5QVVvFxq0tmYnN2j3fTaEU5AvVyKT/1DitNclPAA8B/y7Zvgf4H8CHhruZ5a6mrpp/9dvbOXvyfd78x2N5m4gsH65fuc67R3p490gPldWVtN6WmQZhw+b1Dvoiy2q0jKRyYD9wO/CXwElgMCKm/q/YA2y6ybG7gF0AW7ZsWWq9ZqtGRHB56Mr0aJaBvmHGSqh7BqCisoKGpnrqm+qob6ybXrqrpviyCveImAC2S2oEXgA+Ot9uNzl2N7AbMt0yi6zTLPVGr40y2D+cCfLeIYb6hxm7PlbssgCorKnMhHhjLfUzlr7StXTlNM49IgYl/Rx4AGiUVJG03jcDZwtQn1kqTU5OMnxhhMG+4emW+eWh/M81k6ua+mrqGutoaKqbXtY31nlemhVowXCX1AKMJcFeA3wG+BbwM+BLZEbM7AReLGShZivZ1UtXGewbZqB3kMG+YYbOD+d8Q+18ql1bO92F0tD0QXdKxRpf15gW2byS7cCepN+9DPhhRLws6QjwjKQ/BQ4ATxWwTrMVY3xsfLp7Zaplnq953HOhsjLq1tVOd6FMtcLr1tV6zvdVIJvRMgeBe+fZ/jZwfyGKMlspIoKRgUuzulcuDVwu2EyP8ykrL5v+MrOhqZ66xloamuqpXVvjESurmP8PZpaD61evz+peGewfZmJseUawVFRWzBqRMtUvXttQ49EpdgOHu9lNTExMMHx+ZHoY4mDfEFdHrhb8vJXVlTcMLaxvqqOmrrrg57b0cLibJS4PX5kehjjYN8TwhUsFnYK3uq76hqGFDU0emWL54XC3VWlsdGxWP/lg33DBrvysaaiZPbQwCXPf39QKyeFuqTc5OcnIxUuzRq9cGryc13NIyoxMmdud0ljnkSlWFA53S52rl68x2DvEQNIqHz4/kre50adGpsy8wKe+KTO80CNTrJQ43G1FmxifmDGmPNNfno8x5eVrKqhPhhRODS2sb/LIFFs5HO62YkxNpDU9DLFviJGLl5Y0pnxN1Zo5V2pm+sN902hb6RzuVrJGr43OGoY42De06JtWVNVWzbjQ54NulaoaT3xl6eRwt5IwMTHB8IVLs0avXBnOfSKtmvrqTOt7zrwpHpliq43D3YriysjVWd0rQ+dHsh5TLonatTU3jA/3yBSzDzjcreDGRscY6h+eddl+NmPKVVaWCe8586bUraulvNwhbvZhHO6WV5OTk1wauDw9DHGwb5hLA5c+9JjyivIZF/h80J1S0+CJr8wWy+FuS3LtyvVZwxCH+odvOqZ8vluyNTTVUV1X7eGFZnnmcLesTYxPMHR+eNZl+1cvXbthvxtuyZaEuW/JZrZ8HO42r/luzjxycfZEWjX11WzYvH7W+PD6pnoqqzwyxazYHO4G3PzmzJKoaaihvqmOls3Ns+ZN8S3ZzEqXP52r0Hw3Z74yco26dbU0NNXR2LqOW++8ZXrOFI9MMVt5srlB9q3A3wIbgUlgd0R8R1Iz8CywFTgF/E5EDBSuVFusmTdnHhm4zMTYBDUN1TQ01bOxo5Xb7+3wLdnMUiablvs48EcR8ZqkBmC/pFeA/wDsjYgnJT0BPAF8vXClWjambs58efAyY6PjTIxNZOZPaaxl68e2UFPvkSlmq0E2N8g+B5xLHo9I6gY2AY8An0522wP8HIf7sooIRq+NMj42wfjoOONjE0QE9Y11bLiludjlmVkR5dTnLmkrcC+wD2hLgp+IOCep9SbH7AJ2AWzZsmUptdocEUFVTRVVnsDQzObIupNVUj3wY+BrETGc7XERsTsiOiOis6WlZTE12k24j9zMbiardJC0hkyw/yAink8290pqT55vB/oKU6KZmeVqwXBX5tu3p4DuiPjzGU+9BOxMHu8EXsx/eWZmthjZ9Lk/CPwucEjS68m2/wo8CfxQ0uPAaeDLhSnRzMxylc1omV8CNxs7tyO/5ZiZWT74GzkzsxRyuJuZpZDD3cwshRzuZmYp5HA3M0shh7uZWQo53M3MUsjhbmaWQg53M7MUcribmaWQw93MLIUc7mZmKeRwNzNLIYe7mVkKOdzNzFLI4W5mlkIOdzOzFHK4m5mlUDY3yP6+pD5Jh2dsa5b0iqTjybKpsGWamVkusmm5/w3w2TnbngD2RsQdwN5k3czMSsSC4R4RrwIX52x+BNiTPN4DPJrnuszMbAkW2+feFhHnAJJla/5KMjOzpSr4F6qSdknqktTV399f6NOZmRmLD/deSe0AybLvZjtGxO6I6IyIzpaWlkWezszMcrHYcH8J2Jk83gm8mJ9yzMwsH7IZCvk08P+AOyX1SHoceBJ4WNJx4OFk3czMSkTFQjtExFdu8tSOPNdiZmZ54itUzcxSyOFuZpZCDnczsxRyuJuZpZDD3cwshRzuZmYp5HA3M0shh7uZWQo53M3MUsjhbmaWQg53M7MUcribmaWQw93MLIUc7mZmKeRwNzNLIYe7mVkKOdzNzFLI4W5mlkIOdzOzFFpSuEv6rKRjkk5IeiJfRZmZ2dIsOtwllQN/CXwOuBv4iqS781WYmZkt3lJa7vcDJyLi7YgYBZ4BHslPWWZmthQVSzh2E/DejPUe4F/P3UnSLmBXsnpd0uElnHO5bADOF7uILKyEOldCjeA688115teduR6wlHDXPNvihg0Ru4HdAJK6IqJzCedcFq4zf1ZCjeA688115pekrlyPWUq3TA9w64z1zcDZJfw+MzPLk6WE+6+BOyR1SKoEHgNeyk9ZZma2FIvulomIcUn/Cfh7oBz4fkS8ucBhuxd7vmXmOvNnJdQIrjPfXGd+5VynIm7oJjczsxXOV6iamaWQw93MLIWWJdxLdZoCSd+X1Ddz7L2kZkmvSDqeLJuKWWNS062SfiapW9Kbkr5airVKqpb0z5LeSOr8k2R7h6R9SZ3PJl/AF5WkckkHJL1cqjUCSDol6ZCk16eGw5Xg694o6TlJR5P36CdLsMY7k7/h1M+wpK+VWp1JrX+QfH4OS3o6+Vzl/P4seLiX+DQFfwN8ds62J4C9EXEHsDdZL7Zx4I8i4qPAA8DvJX/DUqv1OvBQRNwDbAc+K+kB4FvAt5M6B4DHi1jjlK8C3TPWS7HGKb8ZEdtnjMcutdf9O8BPIuIu4B4yf9eSqjEijiV/w+3AJ4ArwAuUWJ2SNgG/D3RGxMfIDFZ5jMW8PyOioD/AJ4G/n7H+DeAbhT5vDvVtBQ7PWD8GtCeP24Fjxa5xnppfBB4u5VqBWuA1Mlctnwcq5ns/FKm2zWQ+yA8BL5O5IK+kapxR6ylgw5xtJfO6A2uBd0gGZ5RijfPU/FvAP5ZinXxw5X8zmdGMLwO/vZj353J0y8w3TcGmZTjvYrVFxDmAZNla5HpmkbQVuBfYRwnWmnR3vA70Aa8AJ4HBiBhPdimF1/8vgD8GJpP19ZRejVMC+Kmk/clUHlBar/s2oB/466Sb63uS6kqsxrkeA55OHpdUnRFxBvgz4DRwDhgC9rOI9+dyhHtW0xTYwiTVAz8GvhYRw8WuZz4RMRGZ//puJjO53Efn2215q/qApC8AfRGxf+bmeXYtlffogxFxH5luzd+T9KliFzRHBXAf8N2IuBe4TPG7iW4q6av+IvCjYtcyn6TP/xGgA7gFqCPz2s+14PtzOcJ9pU1T0CupHSBZ9hW5HgAkrSET7D+IiOeTzSVZK0BEDAI/J/MdQaOkqQvmiv36Pwh8UdIpMjOZPkSmJV9KNU6LiLPJso9MH/H9lNbr3gP0RMS+ZP05MmFfSjXO9DngtYjoTdZLrc7PAO9ERH9EjAHPA7/BIt6fyxHuK22agpeAncnjnWT6t4tKkoCngO6I+PMZT5VUrZJaJDUmj2vIvFG7gZ8BX0p2K2qdEfGNiNgcEVvJvBf/b0T8e0qoximS6iQ1TD0m01d8mBJ63SPifeA9SVOzFu4AjlBCNc7xFT7okoHSq/M08ICk2uRzP/X3zP39uUxfEnweeItM/+t/K+YXFnPqeppMv9YYmRbI42T6X/cCx5NlcwnU+W/I/DfsIPB68vP5UqsV+DhwIKnzMPDfk+3bgH8GTpD573BVsf+mSV2fBl4u1RqTmt5Ift6c+uyU4Ou+HehKXvf/DTSVWo1JnbXABWDdjG2lWOefAEeTz9DfAVWLeX96+gEzsxTyFapmZinkcDczSyGHu5lZCjnczcxSyOFuZpZCDnczsxRyuJuZpdD/B9xpaoQEHtpHAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib\n",
    "from matplotlib.patches import Circle, Wedge, Polygon\n",
    "from matplotlib.collections import PatchCollection\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# Fixing random state for reproducibility\n",
    "np.random.seed(19680801)\n",
    "\n",
    "polygon = Polygon(polygon_array, True)\n",
    "\n",
    "fig, ax = plt.subplots()\n",
    "\n",
    "resolution = 50  # the number of vertices\n",
    "\n",
    "patches = []\n",
    "\n",
    "patches.append(polygon)\n",
    "\n",
    "p = PatchCollection(patches, alpha=0.4)\n",
    "p.set_array(np.array(colors))\n",
    "ax.add_collection(p)\n",
    "\n",
    "plt.xlim(0, m)\n",
    "plt.ylim(0, m)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "it works True\n"
     ]
    }
   ],
   "source": [
    "def is_in_poly(x, y, poly_xs, poly_ys):\n",
    "    \"\"\"\n",
    "    whether one point is inside a 2-D poly\n",
    "    :param x: point_x\n",
    "    :param y: point_y\n",
    "    :param poly_xs: xs of poly\n",
    "    :param poly_ys: ys of poly\n",
    "    :return: true or false\n",
    "    \"\"\"\n",
    "    odd_cross = False\n",
    "    for i in range(len(poly_xs)):\n",
    "        j = i - 1 if i > 0 else len(poly_xs) - 1\n",
    "        if poly_ys[i] < y <= poly_ys[j] or poly_ys[j] < y <= poly_ys[i]:\n",
    "            if poly_xs[i] + (y - poly_ys[i]) * (poly_xs[j] - poly_xs[i]) / (poly_ys[j] - poly_ys[i]) < x:  # wont divide 0\n",
    "                odd_cross = False if odd_cross else True\n",
    "    return odd_cross\n",
    "\n",
    "\n",
    "def demo():\n",
    "    \"\"\"\n",
    "    test functional\n",
    "    \"\"\"\n",
    "    print(\"it works\", is_in_poly(5, 5, polygon_array[:,0], polygon_array[:,1]))\n",
    "    \n",
    "demo()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
